1. Field of the Invention
The present invention relates to queue servicing mechanisms. More specifically, the invention provides a system for servicing multiple packet queues.
2. Background
Various procedures and devices are used to transmit data between nodes in a network. For example, data may be transmitted through multiple intermediate network communication devices, such as routers and switches, located between a source node and a destination node. These intermediate network communication devices may contain one or more queues that temporarily store data awaiting transmission to another node or network communication device in the network.
In networks that transmit data using an Internet Protocol (IP), best-effort service is typically provided by the various network nodes. Best-effort service does not provide any Quality of Service (QOS) guarantees for a particular data stream. Instead, best-effort service transmits data in the order it was received using the node's available bandwidth. Thus, during heavy network usage periods, data may travel slowly and require a significant amount of time to travel from the source node to the destination node. However, during light network usage periods, the same data may travel through the network quickly such that the data reaches the destination node in a shorter period of time.
Since IP data is typically transmitted using best-effort service, the speed at which IP data travels through a network depends on the available bandwidth between the source node and the destination node. Thus, the time required to transmit IP data through a network may vary significantly. Therefore, best-effort service is not practical for transmitting real-time IP data such as voice data or real-time image data. Instead, QOS routing and resource allocation should be utilized when transmitting real-time IP data.
Network communication devices that support QOS and resource allocation typically use multiple queues in which each queue is associated with a particular QOS or a particular data flow. A portion of the device's resources, such as bandwidth, are allocated to a particular queue within the device. Since IP data packets may have different sizes (i.e., lengths), network communication devices that contain multiple queues require a mechanism or procedure for servicing those queues. Known systems utilize a time stamp associated with each data packet at the arrival time to the various queues. The queues are serviced based on the queue priority and the time stamp of the data packets stored in the queue. This use of a time stamp for each data packet increases the complexity of the queue servicing procedure by requiring the generation and maintenance of time stamps. Additionally, the queue servicing procedure is complicated by requiring the comparison of multiple time stamps to determine the next queue or data packet to service.